#include "headfiles.h"

bool calcKthElem(int *a, int m, int *b, int n, int k, int &elem) {
    if (m + n < k) {
        return false;
    }

    if (k < 0) {
        return false;
    }
    
    int i, j;
    int la, ra, lb, rb;
    int remaining_k = k;
    double temp_a, temp_b;

    la = 0;
    ra = m;

    lb = 0;
    rb = n;

    while (true) {
        temp_a = (ra - la);
        temp_b = (rb - lb);
        i = (int)(temp_a/(temp_a + temp_b) * (remaining_k - 1));
        j = remaining_k - i - 1;
        i += la;
        j += lb;

        if (a[i] < b[j]) {
            if (j == 0) {
                elem = a[i];
                return true;
            }
            else if (a[i] > b[j - 1]) {
                elem = a[i];
                return true;
            }
            else { // a[i] < b[j - 1]
                la = i + 1;
                rb = j;
                remaining_k = remaining_k - i - 1;
            }
        }
        else { // a[i] > b[j]
            if (i == 0) {
                elem = b[j];
                return true;
            }
            else if (b[j] > a[i - 1]) {
                elem = b[j];
                return true;
            }
            else { // b[j] < a[i - 1]
                lb = j + 1;
                ra = i;
                remaining_k = remaining_k - j - 1;
            }
        }
    }

    return false;
}

